
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1752. -- [Usaco2005 qua]Til the Cows Come Home -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1752: [Usaco2005 qua]Til the Cows Come Home</h2><span class=green>Time Limit: </span>5 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>43&nbsp;&nbsp;<span class=green>Solved: </span>26<br>[<a href='submitpage.php?id=1752'>Submit</a>][<a href='problemstatus.php?id=1752'>Status</a>][<a href='bbs.php?id=1752'>Discuss</a>]</center><h2>Description</h2><div class=content>
Bessie is out in the field and wants to get back to the barn to get
as much sleep as possible before Farmer John wakes her for the
morning milking. Bessie needs her beauty sleep, so she wants to get
back as quickly as possible.

Farmer John's field has N (2 <= N <= 1000) landmarks in it, uniquely
numbered 1..N. Landmark 1 is the barn; the apple tree grove in which
Bessie stands all day is landmark N.  Cows travel in the field using
T (1 <= T <= 2000) bidirectional cow-trails of various lengths
between the landmarks. Bessie is not confident of her navigation
ability, so she always stays on a trail from its start to its end
once she starts it.

Given the trails between the landmarks, determine the minimum
distance Bessie must walk to get back to the barn.  It is guaranteed
that some such route exists.

</div><h2>Input</h2><div class=content>
* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three space-separated
        integers.  The first two integers are the landmarks between
        which the trail travels. The third integer is the length of
        the trail, range 1..100.

</div><h2>Output</h2><div class=content>
* Line 1: A single integer, the minimum distance that Bessie must
        travel to get from landmark N to landmark 1.

</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
5 5<br />
1 2 20<br />
2 3 30<br />
3 4 20<br />
4 5 20<br />
1 5 100<br />
<br />
INPUT DETAILS:<br />
<br />
There are five landmarks.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
90<br />
<br />
OUTPUT DETAILS:<br />
<br />
Bessie can get home by following trails 4, 3, 2, and 1.<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search=Gold'>Gold</a></p></div><center>[<a href='submitpage.php?id=1752'>Submit</a>][<a href='problemstatus.php?id=1752'>Status</a>][<a href='bbs.php?id=1752'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
